/*
 * @Author: your name
 * @Date: 2021-10-12 10:07:24
 * @LastEditTime: 2021-10-12 15:43:59
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\模板问题\P1060 开心的金明\main.cpp
 */
#include<iostream>
using namespace std;
#include<stdlib.h>

#define max(x,y) (x < y) ? y : x

typedef struct{
    int price;
    int importance;
    int value;
}obj;

const int N = 30;
const int M = 30010;
int main(){
    int n,m;
    //钱数 物品数
    cin >> m >> n;
    obj** o = (obj**)malloc(sizeof(obj*)*(n+2));
    if(!o) exit(-1);
    for(int i=1; i<=n; i++){
        o[i] = (obj*)malloc(sizeof(obj));
        if(!o[i]) exit(-1);
        //价格 重要度
        cin >> o[i]->price >> o[i]->importance;
        //价值
        o[i]->value = o[i]->price*o[i]->importance;
    }

    // for(int i=1; i<=n; i++){
    //     cout << o[i]->price << " " << o[i]->importance << " " << o[i]->value << endl;
    // }
    int f[N][M] = {0};
    //动态规划
    for(int i=1; i<=n; i++){
        //遍历物品
        for(int j=0; j<=m; j++){
            if(j >= o[i]->price){
                //能放入i物品 取放入和不放入的较大值
                f[i][j] = max(f[i-1][j] , f[i-1][j-o[i]->price]+o[i]->value);
            }else{
                //不能放入i物品
                f[i][j] = f[i-1][j];
            }
        }
        // for(int j=0; j<=m; j++){
        //     cout << "obj:" << i << " v:" << j << " => " << f[i][j] << endl;
        // }
        // cout << endl;
        // if(i==3) exit(-1);
    }
    cout << f[n][m] << endl;
    return 0;
}
